package array.elementRemove;

import java.util.Stack;

/**
 * @Author: 海琳琦
 * @Date: 2021/12/13 17:18
 *
 * 给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，请你判断二者是否相等。# 代表退格字符。
 * 如果相等，返回 true ；否则，返回 false 。
 *
 * 示例 3：
 * 输入：s = "a##c", t = "#a#c"
 * 输出：true
 * 解释：s 和 t 都会变成 “c”。
 *
 * 进阶：
 *
 * 你可以用 O(N) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/backspace-string-compare
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Title844 {
    public static void main(String[] args) {

    }

    /**
     * 暴力1 Stack
     * @param s
     * @param t
     * @return
     */
    private boolean backspaceCompare(String s, String t) {
        Stack<Character> leftS = new Stack<>();
        Stack<Character> rightS =new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i)!='#'){
                leftS.push(s.charAt(i));
            }else{
                if (!leftS.isEmpty()) {
                    leftS.pop();
                }
            }
        }
        for (int i = 0; i < t.length(); i++) {
            if(t.charAt(i)!='#'){
                rightS.push(t.charAt(i));
            }else{
                if (!rightS.isEmpty()) {
                    rightS.pop();
                }
            }
        }
        if (leftS.size()!=rightS.size()){
            return false;
        }
        for (int i = 0; i < leftS.size(); i++) {
            if (!leftS.get(i).equals(rightS.get(i))) {
                return false;
            }
        }
        return true;
    }

    /**
     * 暴力2 用字符串代替Stack
     * @param s
     * @param t
     * @return
     */
    private boolean backspaceCompare1(String s, String t) {
        StringBuilder a = new StringBuilder();
        StringBuilder b = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != '#') {
                a.append(s.charAt(i));
            }else if(a.length()!=0){
                a.deleteCharAt(a.length() - 1);
            }
        }
        for (int i = 0; i < t.length(); i++) {
            if (t.charAt(i) != '#') {
                b.append(t.charAt(i));
            }else if(b.length()!=0){
                b.deleteCharAt(b.length() - 1);
            }
        }
        return a.toString().equals(b.toString());
    }

    /**
     * 双指针 空间复杂度O(1)
     * @param s
     * @param t
     * @return
     */
    private boolean backspaceCompare2(String s, String t) {
        return false;
    }

}
